package com.leetcode.no739;

import java.util.HashMap;
import java.util.Stack;
import java.util.Arrays;

public class Solution {
    // labuladong 单调栈
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        if (len <= 1) {
            return new int[len];
        }
        int[] res = new int[len];
        Stack<Integer> stack = new Stack<>();

        // 启动元素
        // stack.push(T[0]);

        // 元素的索引挨个入栈  求它们之间的间距
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.empty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }

            // 得到索引间距
            res[i] = stack.empty() ? 0 : (stack.peek() - i);

            // 将该索引放入栈中
            stack.push(i);
        }

        return res;
    }


    // 暴力解
    public int[] dailyTemperatures01(int[] T) {
        int len = T.length;
        int[] ans = new int[len];
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        for (int i = len - 1; i >= 0; --i) {
            int warmerIndex = Integer.MAX_VALUE;
            for (int t = T[i] + 1; t <= 100; ++t) {
                if (next[t] < warmerIndex) {
                    warmerIndex = next[t];
                }
            }
            if (warmerIndex < Integer.MAX_VALUE) {
                ans[i] = warmerIndex - i;
            }
            next[T[i]] = i;
        }
        return ans;
    }

    //
    public int[] dailyTemperatures02(int[] T) {
        int len = T.length;
        if (len <= 1) {
            return new int[len];
        }

        int[] res = new int[len];

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int prevIndex = stack.pop();
                res[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return res;
    }
}


//class Solution:
//    def dailyTemperatures(self, T: List[int]) -> List[int]:
//        n=len(T)
//        ans=[0]*n
//        for i in range(n-2,-1,-1):
//            now=i+1
//            while T[now]<=T[i]:
//                if ans[now]:
//                    now+=ans[now]
//                else:
//                    break
//            else:
//                ans[i]=now-i
//        return ans